package leetcode.hot100;

import leetcode.common.TreeNode;

import java.util.HashMap;

@SuppressWarnings("all")
public class _105_从前序与中序遍历序列构造二叉树 {

    // 记录中序遍历结点的索引
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    int[] preorder;
    int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 默认两个数组都是有元素的
        this.preorder = preorder;
        this.inorder = inorder;
        for (int i = 0; i < inorder.length; i++) {
            hashMap.put(inorder[i], i);
        }
        return build(0, 0, inorder.length - 1);
    }

    private TreeNode build(int rootIdx, int left, int right) {
        if (left > right) return null;
        // 构建二叉树结点
        TreeNode root = new TreeNode(preorder[rootIdx]);
        // 找到根结点在中序遍历中的位置，以此划分处左子树和右子树
        int i = hashMap.get(preorder[rootIdx]);
        // 左子树的范围大小
        int len = i - left;
        // 获取左子树的根结点和中序遍历范围
        root.left = build(rootIdx + 1, left, i - 1);
        // 获取右子树的根结点和中序遍历范围
        root.right = build(rootIdx + 1 + len, i + 1, right);
        return root;
    }
}
